package com.lwx.algorithm.chapter6;

import com.lwx.tree.TreeNode;

import java.util.*;

public class Offer102 {
    public static void main(String[] args) {
        TreeNode t = new TreeNode(1, null, null);
        TreeNode t2 = new TreeNode(2, null, null);
        TreeNode root = new TreeNode(3, t, t2);
        Offer102 o = new Offer102();
        List<List<Integer>> ret = o.levelOrder(root);
        System.out.println(ret);

    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList();
        if(root == null){
            return ret;
        }
        // treenode,第几层
        Queue<Map<TreeNode,Integer>> queue = new LinkedList<>();
        Map map = new HashMap();
        map.put(root,0);
        queue.add(map);
        while (!queue.isEmpty()){
            Map<TreeNode, Integer> topMap = queue.poll();
            Iterator<Map.Entry<TreeNode, Integer>> iterator = topMap.entrySet().iterator();
            if (iterator.hasNext()){
                Map.Entry<TreeNode, Integer> entry = iterator.next();
                TreeNode currentNode = entry.getKey();
                Integer value = entry.getValue();
                List<Integer> levelTreeNodes;
                //如果不catch，因为ret里面的元素没有初始化，树的层级是多少不知道，所以会出现数组越界错误
                try{
                    levelTreeNodes = ret.get(value);
                }catch (IndexOutOfBoundsException e){
                    ret.add(value,new ArrayList<>());
                }
                levelTreeNodes = ret.get(value);

                levelTreeNodes.add(currentNode.getVal());
                if(null !=currentNode.getLeft()){
                    Map subLevelMap = new HashMap();
                    subLevelMap.put(currentNode.getLeft(), value+1);
                    queue.offer(subLevelMap);
                }
                if(null !=currentNode.getRight()){
                    Map subLevelMap = new HashMap();
                    subLevelMap.put(currentNode.getRight(), value+1);
                    queue.offer(subLevelMap);
                }
            }

        }
        return ret;
    }
}
